Nash-Williams theorem

Short description: Theorem in graph theory describing number of edge-disjoint spanning trees a graph can have

In graph theory, the Nash-Williams theorem is a tree-packing theorem that describes how many edge-disjoint spanning trees (and more generally forests) a graph can have:

A graph G has t edge-disjoint spanning trees iff for every partition

$V_1,\dots ,V_k\subset V(G)$

where

$V_i\ne \mathrm{\varnothing }$

there are at least t(k − 1) crossing edges.

The theorem was proved independently by Tutte and Nash-Williams, both in 1961. In 2012, Kaiser gave a short elementary proof.

For this article, we say that such a graph has arboricity t or is t-arboric. (The actual definition of arboricity is slightly different and applies to forests rather than trees.)

Related tree-packing properties

A k-arboric graph is necessarily k-edge connected. The converse is not true.

As a corollary of the Nash-Williams theorem, every 2k-edge connected graph is k-arboric.

Both Nash-Williams' theorem and Menger's theorem characterize when a graph has k edge-disjoint paths between two vertices.

Nash-Williams theorem for forests

In 1964, Nash-Williams generalized the above result to forests:

A graph

$G$

can be partitioned into

$t$

edge-disjoint forests iff for every

$U\subset V(G)$

, the induced subgraph

$G[U]$

has at most

$t(|U|-1)$

edges.

Other proofs are given here.

This is how people usually define what it means for a graph to be t-arboric.

In other words, for every subgraph

$S=G[U]$

, we have

$t\ge \lceil E(S)/(V(S)-1)\rceil$

. It is tight in that there is a subgraph

$S$

that saturates the inequality (or else we can choose a smaller

$t$

). This leads to the following formula

$t=\lceil \underset{S\subset G}{\max }\frac{E(S)}{V(S)-1}\rceil$

,

also referred to as the Nash-Williams formula.

The general problem is to ask when a graph can be covered by edge-disjoint subgraphs.

See also

• Arboricity
• Bridge (cut edge)
• Matroid partitioning
• Menger's theorem
• Tree packing conjecture

External links

• Paulson, Lawrence C. The Nash-Williams partition theorem (Formal proof development in Isabelle/HOL, Archive of Formal Proofs)